import java.util.LinkedList;
import java.util.Queue;

public class Tree {
        public static class BTNode {
            public char val;
            public BTNode left;
            public BTNode right;

            public BTNode(char val) {
                this.val = val;
            }
        }
        //创建二叉树
    /*public BTNode createBinaryTree() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
        return node1;
    }*/

        //创建二叉树
        public int i = 0;
        public BTNode createBinaryTree(String str) {
            BTNode root = null;
            if (str.charAt(i) != '#') {
                root = new BTNode(str.charAt(i));
                i++;
                root.left = createBinaryTree(str);
                root.right = createBinaryTree(str);
            } else {
                i++;
            }
            return root;
        }

        // 前序遍历
        void preOrder(BTNode root) {
            if (root == null) return;
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }

        // 中序遍历
        void inOrder(BTNode root) {
            if (root == null) return;
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }

        // 后序遍历
        void postOrder(BTNode root) {
            if (root == null) return;
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }

        //求节点个数
        //遍历思路
        public static int nodeSize = 0;
        public void size(BTNode root) {
            if (root == null) return;
            nodeSize++;
            size(root.left);
            size(root.right);
        }

        //子问题思路
        public int size2(BTNode root) {
            if (root == null) return 0;
            return size2(root.left) + size2(root.right) + 1;
        }

        //求叶子节点的个数
        //遍历思路
        public static int leafNodeCount = 0;
        public void getLeafNodeCount(BTNode root) {
            if (root == null) return;
            if (root.left == null && root.right == null) {
                leafNodeCount++;
            }
            getLeafNodeCount(root.left);
            getLeafNodeCount(root.right);
        }

        //子问题思路
        public int getLeafNodeCount2(BTNode root) {
            if (root == null) return 0;
            if (root.left == null && root.right == null) {
                return 1;
            }
            return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
        }

        //求第K层节点的个数
        //子问题思路
        public int getLevelNodeCount(BTNode root, int k) {
            if (root == null) return 0;
            if (k == 1) return 1;
            return getLevelNodeCount(root.left, k-1) + getLevelNodeCount(root.right, k-1);
        }

        // 获取二叉树的高度
        public int getHeight(BTNode root) {
            if (root == null) return 0;
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }

        // 检测值为value的元素是否存在
        //前序遍历的方法
        public BTNode find(BTNode root, int val) {
            if (root == null) return null;
            if (root.val == val) return root;
            find(root.left ,val);
            find(root.right ,val);
            return null;
        }


        //反转二叉树
        public BTNode invertTree(BTNode root) {

            if (root == null) return null;

            BTNode tmp = root.left;

            root.left = root.right;

            root.right = tmp;

            invertTree(root.left);

            invertTree(root.right);

            return root;
        }

        public boolean isSameTree(BTNode p, BTNode q) {
            //结构不相同的情况
            if (p == null && q != null || p != null && q == null) {
                return false;
            }
            //结构相同但为空
            if (p == null && q == null) {
                return true;
            }
            //结构相同值不同
            if (p.val != q.val) {
                return false;
            }
            //值相同
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }

        //判断是否是完全二叉树
        public boolean isTruelyBinaryTree(BTNode root) {
            if (root == null) return true;
            Queue<BTNode> queue = new LinkedList<>();
            queue.offer(root);
            BTNode cur = null;

            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (cur == null) {
                    break;
                }
                queue.offer(cur.left);
                queue.offer(cur.right);
            }

            while (!queue.isEmpty()) {
                cur = queue.peek();
                if (cur != null) {
                    return false;
                }
                queue.poll();
            }
            return true;
        }
    public String tree2str(BTNode root) {
     StringBuilder stringBuilder = new StringBuilder();
     tree2strChild(root, stringBuilder);
     return stringBuilder.toString();
    }

     public void tree2strChild(BTNode root, StringBuilder stringBuilder) {
        stringBuilder.append(root.val);
        if (root.left != null) {
            stringBuilder.append("(");
            tree2strChild(root.left, stringBuilder);
            stringBuilder.append(")");
        } else {
        if (root.right != null) {
            stringBuilder.append("()");
        } else {
        return;
        }
        }
        if (root.right != null) {
            stringBuilder.append("(");
            tree2strChild(root.right, stringBuilder);
            stringBuilder.append(")");
        } else {
        return;
        }
        }
}
